/*  
 * i-OSGi - Tunable Bundle Isolation for OSGi
 * Copyright (C) 2011  Sven Schulz
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.iosgi.benchmark;

import java.io.File;
import java.io.FileWriter;
import java.util.Random;
import java.util.concurrent.TimeUnit;

import org.apache.felix.ipojo.annotations.Component;
import org.apache.felix.ipojo.annotations.Provides;
import org.iosgi.impl.engine.CompetitionColorer;
import org.iosgi.impl.engine.PseudoBooleanColorer;
import org.iosgi.impl.engine.ReportingColorer;
import org.iosgi.impl.engine.ReportingColorer.ReportListener;
import org.iosgi.impl.engine.RoundBasedIteratedGreedyColorer;
import org.jgrapht.VertexFactory;
import org.jgrapht.ext.MatrixExporter;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import algorithms.graphColorer.Colorer;
import dataStructures.graph.Edge;
import dataStructures.graph.ExtendedSimpleGraphAjazenzList;
import dataStructures.graph.ExtendedUndirectedGraph;
import dataStructures.graph.GraphColoring;

/**
 * @author Sven Schulz
 */
@Component(immediate = true)
@Provides(specifications = { Benchmark.class })
public class MIPSolving implements Benchmark {

	private static final Logger LOGGER = LoggerFactory
			.getLogger(MIPSolving.class);

	private static class NumberVertexFactory implements VertexFactory<String> {

		int i = 0;

		@Override
		public String createVertex() {
			return Integer.toString(i++);
		}

	}

	private static ExtendedUndirectedGraph<String, Edge<String>> createRandomGraph(
			int vertices, int edges, Random random) {
		RandomGraphGenerator<String, Edge<String>> rgg = new RandomGraphGenerator<String, Edge<String>>(
				vertices, edges, false, random);
		ExtendedUndirectedGraph<String, Edge<String>> graph = new ExtendedSimpleGraphAjazenzList<String>();
		rgg.generateGraph(graph, new NumberVertexFactory(), null);
		return graph;
	}

	static int arithmeticSeriesSum(int n, int first, int d) {
		return n * (2 * first + (n - 1) * d) / 2;
	}

	@SuppressWarnings("unchecked")
	@Override
	public void perform() throws Exception {
		/* Create file for benchmark data. */
		File root = new File(Long.toHexString(System.currentTimeMillis()));
		root.mkdir();
		MatrixExporter<String, Edge<String>> exp = new MatrixExporter<String, Edge<String>>();
		int reps = 10;
		long timeout = 60000;
		for (int r = 1; r <= reps; r++) {
			Random random = new Random(r);
			LOGGER.debug("starting repetition {}/{}", r, reps);
			for (int i = 2; i <= 16; i += 2) {
				int vertices = 16 * i;
				for (int j = 0; j <= 10; j += 1) {
					int maxEdges = arithmeticSeriesSum(vertices - 1, 1, 1);
					int edges = (int) ((j / 10.0) * maxEdges);
					String id = r + "-" + vertices + "-" + edges;
					LOGGER.debug(
							"performing benchmark on graph (ID={},|V|={},|E|={},TO={} ms)",
							new Object[] { id, vertices, edges, timeout });
					long ref = System.currentTimeMillis();
					ExtendedUndirectedGraph<String, Edge<String>> graph = createRandomGraph(
							vertices, edges, random);
					long elapsed = System.currentTimeMillis() - ref;
					LOGGER.debug(
							"graph generated (|V|={},|E|={}/{}[{} %],t={} ms)",
							new Object[] {
									graph.vertexSet().size(),
									graph.edgeSet().size(),
									maxEdges,
									(double) graph.edgeSet().size() / maxEdges
											* 100.0, elapsed });
					File f = new File(root, id + ".graph");
					exp.exportAdjacencyMatrix(new FileWriter(f), graph);
					LOGGER.debug("exported to {}", f.getAbsolutePath());
					ReportingColorer<String, Edge<String>> colorer = new CompetitionColorer<String, Edge<String>>(
							new PseudoBooleanColorer<String, Edge<String>>(
									graph),
							new RoundBasedIteratedGreedyColorer<String, Edge<String>>(
									graph, Integer.MAX_VALUE));
					final Object[] best = new Object[2];
					best[0] = Integer.MAX_VALUE;
					long baseref = System.nanoTime();
					colorer.getColoring(
							new ReportListener<String, Edge<String>>() {
								@Override
								public void handle(
										Colorer<String, Edge<String>> colorer,
										GraphColoring<String, Edge<String>> coloring) {
									int colors = coloring.getNumberOfColors();
									synchronized (best) {
										if (((Integer) best[0]) > colors) {
											best[0] = colors;
											best[1] = colorer.getClass()
													.getSimpleName();
										}
									}
								}
							}, timeout, TimeUnit.MILLISECONDS);
					LOGGER.debug(
							"{} was first best with {} colors on (|V|={},|E|={}) in {} ns",
							new Object[] { best[1], best[0], vertices, edges,
									System.nanoTime() - baseref });
					Runtime.getRuntime().gc();
				}
			}
		}
	}

	public static void main(String[] args) throws Exception {
		MIPSolving s = new MIPSolving();
		s.perform();
	}

}